A. Field of the Invention
The present invention relates generally to computing devices, and more particularly, to loadbalancing of computing devices.
B. Description of the Related Art
The World Wide Web (“web”) contains a vast amount of information. Search engines assist users in locating desired portions of this information by cataloging web pages. Typically, in response to a user's request, the search engine returns references to documents relevant to the request.
Search engines may base their determination of the user's interest on search terms (called a search query) entered by the user. The goal of the search engine is to identify links to high quality relevant results based on the search query. Typically, the search engine accomplishes this by matching the terms in the search query to a corpus of pre-stored web documents. Web documents that contain the user's search terms are considered “hits” and are returned to the user.
The corpus of pre-stored web documents may be stored by the search engine as an index of terms found in the web pages. The index may be formed as an inverted index data structure that stores, for each term, a list of all documents that contain the term. In the context of the web, such an index can be very large, such as one covering three billion or more documents. Such a large data structure will generally not fit on one device, but instead may be partitioned over multiple devices (“back end devices”). Given a user search query to a “front end” device, the search request is then sent to the back end devices. Each back end device may perform a search over its portion of the data structure and return its results to the front end device.
Different search requests may take varying amounts of time on different parts of the index. It is possible that the search request over one portion of the index can be completed very quickly for most of the searches while taking a longer time on different portions of the index. In this situation, the device servicing the “slow” portion of the index can become a bottleneck that may tend to slow down the other devices.